package test;
import java.util.ArrayList;
import java.util.List;

public class test3_2 {
    public static void main(String[] args) {
        int limit = 20000; // 设置素数范围
        printPrimes(limit);
    }

    public static void printPrimes(int limit) {
        List<Integer> primes = sieveOfEratosthenes(limit);
        int count = 0; // 记录当前行打印的素数个数

        for (int prime : primes) {
            System.out.printf("%d ", prime);
            count++;
            if (count % 5 == 0) {
                System.out.println(); // 每行打印5个素数换行
            }
        }

        // 如果最后一行没有换行
        if (count % 5 != 0) {
            System.out.println();
        }
    }

    public static List<Integer> sieveOfEratosthenes(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        List<Integer> primes = new ArrayList<>();

        // 初始化数组，假设所有数都是素数
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }

        // 筛选合数
        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int multiple = p * p; multiple <= limit; multiple += p) {
                    isPrime[multiple] = false; // 标记为合数
                }
            }
        }

        // 收集素数
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }

        return primes;
    }
}
